# 遇到的
# 数组排序
注：假设有大到小
/ 冒泡排序
// 双循环逐一比较两个元素，交换顺序
// 时间复杂度：O(n^2)，空间复杂度：O(1)
function sort1(arr) {
const len = arr.length
for (let i = 0; i < len; i++) {
for (let j = i + 1; j < len; j++) {
if (arr[j] > arr[i]) {
[arr[i], arr[j]] = [arr[j], arr[i]]
}
}
}
return arr
}
console.log('冒泡排序', sort1([1,3,2,7,5,8,4]))
// 插入排序
// 类比摸扑克牌的过程，新摸到的牌比手中的大则放到前边，新摸到的比手中的小则放到后边
// 时间复杂度：O(n^2)，空间复杂度：O(n)
function sort2(arr) {
let hand = [arr[0]]
let arrLen = arr.length
for (let i = 1; i < arrLen; i++) {
const handLen = hand.length
if (arr[i] >= hand[handLen - 1]) {
hand.push(arr[i])
} else if (arr[i] <= hand[0]) {
hand.unshift(arr[i])
} else {
for (let j = 0; j < handLen - 1; j++) {
if (arr[i] >= hand[j] && arr[i] <= hand[j + 1]) {
hand.splice(j + 1, 0, arr[i])
break
}
}
}
}
return hand
}
console.log('插入排序', sort2([2,1,4,6,8,3,2,4,6,73,2,4,6]))
// 快速排序
// 找到数组中间位置的元素，拿每个元素与中间元素比，大的放左边数组中，小的方右边数组中，针对新数组重复该操作
// 时间复杂度：O(n)，空间复杂度：O(n)
function sort3(arr) {
const len = arr.length
if (len <= 1) {
return arr
}
let middle = Math.floor(len/2)
let mdlItm = arr[middle-1]
arr.splice(middle-1, 1)
const leftArr = [], rightArr = []
for (let i = 0; i < len -1; i++) {
if (arr[i] < mdlItm) {
leftArr.push(arr[i])
} else {
rightArr.push(arr[i])
}
}
return sort3(leftArr).concat(mdlItm, sort3(rightArr))
}
console.log('快速排序', sort3([3,12,4,6,73,5,6,3,5,72,4]))
# 数组去重
Set
function unique(arr) { return [...new Set(arr)] // return Array.from(new Set(arr)) }indexOf、filter (indexOf获取元素在数组中首次出现的位置，只有唯一的元素其indexOf位置才与遍历时的index相等) O(n)
function unique(arr) { return arr.filter((item, index, arr) => { return arr.indexOf(item) === index }) }检查是否重复，放入新数组
// includes检查重复 O(n^2) function unique(arr) { let result = [] let len = arr.length for (let i = 0; i < len; i++) { let item = arr[i] if (!result.includes(item)) { // includes内部使用了while循环(其实indexOf也是这样) result.push(item) } } return result } // 对象key值检查重复 O(n) function unique(arr) { let obj = {} let result = [] let len = arr.length for (let i = 0; i < len; i++) { let item = arr[i] if (!obj[item]) { result.push(item) obj[item] = 1 } else { obj[item] += 1 } } return result } // 等价于 reduce 实现 O(n) let hash = {} function unique(arr, initialVal) { return arr.reduce(function(previousVal, currentVal, index, array) { if (!hash[currentVal]) { previousVal.push(currentVal) hash[currentVal] = 1 } else { hash[currentVal] += 1 } return previousVal }, initialVal) } unique(['js', 'css', 'js', 'html'], [])
# 数组扁平化
- 字符串化
利用数组的 toString 方法(或数组与字符串的隐式转化)，将数组转化为字符串，再用 split 将字符串还原为数组
function flatten(arr) {
arr = arr.toString() // 或者隐式转化 arr += ''
return arr.split(',')
}
ES6 flat
function flatten(arr) { return arr.flat(Infinity) }递归
// concat function flatten(arr) { let result = [] let len = arr.length for (let i = 0; i < len; i++) { let item = arr[i] if (Array.isArray(item)) { result = result.concat(flatten(item)) } else { result.push(item) } } return result } // reduce、concat function flatten(arr) { return arr.reduce((result, curItem) => { curItem = Array.isArray(curItem) ? flatten(curItem) : curItem return result.concat(curItem) }, []) } // 普通递归 function flatten() { let ret = []; let toArr = function(arr){ arr.forEach(function(item){ item instanceof Array ? toArr(item) : ret.push(item); }); } toArr(arr); return ret; }结构运算符
function flatten(arr) { while (arr.some(item => Array.isArray(item))) { arr = [].concat(...arr) } return arr }
# 找出数组中第一个不重复的元素
// 当前元素在去除该元素的数组中是否存在
function getFirstUnique(arr) {
let len = arr.length
let target = ''
for (let i = 0; i < len; i++) {
let item = arr[i]
let newArr = [].concat(arr.slice(0, i), arr.slice(i+1))
if (!newArr.includes(item)) {
target = item
break
}
}
return target
}
# 找出数组中第一个不重复的元素
# 剑指offer的
# 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。（简单）
// 思路：栈（先进后出，数组），队列（先进先出）。从栈1取出数据放入栈2，就实现了第一个入栈1的数据，成了最后一个入栈2的数据。
// 定义栈，并实现栈的三种方法
function Stack() {
var item = []
this.push = function(node) {
item.push(node)
}
this.pop = function() {
return item.pop()
}
this.isEmpty = function() {
return item.length === 0
}
}
var stack1 = new Stack()
var stack2 = new Stack()
function push(node) {
// write code here
stack1.push(node)
}
function pop() {
// write code here
if (stack1.isEmpty() && stack2.isEmpty()) {
console.log('Queue is empty')
}
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop())
}
}
console.log(stack2.pop())
}
# 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组[3,4,5,1,2]为[1,2,3,4,5]的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
// 思路：首先理解“非递减排序”，是指有增有平，例如[1,2,3,3,4,5]为非递减。其次观察旋转数组[3,3,4,5,1,2]特点，旋转后非递减性被破坏了，那么比前边数字小的那个数即为最小数。